package com.techyuan.algorithm.sorts;

import static com.techyuan.algorithm.utils.SortUtils.swap;

/**
 * 堆排序
 * @author derek.tian on 2016/11/27.
 */
public class HeapSort implements ISort {
    public int[] sort(int[] sortingArr) {
        heapSort(sortingArr);
        return sortingArr;
    }

    /**
     * 维护最大堆
     *
     * @param sortArr
     * @param i
     */
    public void maxHeapify(int[] sortArr, int heapSize, Integer i) {
        int largest;
        int l = getLeftIndex(i);
        int r = getRightndex(i);
        if (l <= heapSize && sortArr[l - 1] > sortArr[i - 1])
            largest = l;
        else
            largest = i;
        if (r <= heapSize && sortArr[r - 1] > sortArr[largest - 1])
            largest = r;
        if (largest != i) {
            swap(sortArr, i - 1, largest - 1);
            maxHeapify(sortArr, heapSize, largest);
        }
    }

    public void buildMaxHeap(int[] sortArr) {
        int heapSize = sortArr.length;
        for (int i = (int) Math.floor(heapSize / 2); i > 0; i--) {
            maxHeapify(sortArr, heapSize, i);
        }
    }

    public void heapSort(int[] sortArr) {
        buildMaxHeap(sortArr);
        int heapSize = sortArr.length;
        for (int i = heapSize; i > 1; i--) {
            swap(sortArr, 0, i - 1);
            heapSize = heapSize - 1;
            maxHeapify(sortArr, heapSize, 1);
        }
    }

    private int getParentIndex(int index) {
        return index >> 1;
    }

    private int getLeftIndex(int index) {
        return index << 1;
    }

    private int getRightndex(int index) {
        return (index << 1) + 1;
    }
}
